Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-isis-multilevel-routing-00.txt < prev next >

Wrap

Text File | 1993-08-09 | 24.2 KB | 628 lines

ISIS Working Group Radia Perlman Internet-draft Chris Gunner Digital Equipment Corp. June 1993 Multiple Levels of Hierarchy with IS-IS Table of Contents 1. Status of this Memo 2 2. Abstract 2 3. Introduction 2 4. Topologies 3 5. Management 4 5.1. Port/Region Mapping 5 5.2. Address Summaries for Import Into Region 5 6. Extra Information in Control Packets 6 6.1. Hello, CSNP, PSNP 6 6.2. LSP 7 7. Using Address Summaries 7 8. Picking a Path 8 9. Working Group Information 9 10. Authors' Addresses 10 Perlman (Internet-Draft expires end December 1993) [Page 1] Internet-Draft Multilevel IS-IS June 1993 1. Status of this Memo This document is an Internet Draft describing changes to IS-IS to enable it to support many levels of hierarchy. This should apply to any network layer protocol routed by IS-IS. It is not a finished specification. Instead it is a conceptual document, intended to start discussion. If the basic premise is judged sound, it should not be difficult to produce a specification. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. This Internet draft expires at the end of December 1993. Internet drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress". Please check the I-D abstract listing contained in each Internet Draft directory to learn the current status of this or any other Internet Draft. This is a draft document of the ISIS working group. Distribution of this memo is unlimited. Please send comments to the ISIS working group: isis@merit.edu 2. Abstract This paper describes the management, algorithms, and control packet structures necessary to support arbitrary levels of routing hierarchy in IS-IS. 3. Introduction IS-IS is written as though there were two levels of routing hierarchy: level 1, which routes on ID, and level 2, which routes on address prefix. IP and CLNP addressing both have the ability to have multiple levels of hierarchy for "level 2" routing. In IP this is done by summarizing addresses with a shorter mask. In CLNP this is done by summarizing addresses with a shorter address prefix. This document explains what is needed in IS-IS to truly support as many levels of hierarchy as is Perlman (Internet-Draft expires end December 1993) [Page 2] Internet-Draft Multilevel IS-IS June 1993 possible in the address structure. The main reason to provide multiple levels of hierarchy is for scaling. However, the design in this paper also provides a lot of the functionality that people expect from an inter-domain routing protocol. It allows setting up policies for which destinations are reachable from which portions of the network. In cases where the topology and IS-IS can accommodate all the necessary policies, it is desirable to run only a single routing protocol, rather than needing both an intradomain and an interdomain routing protocol. The basic idea is that a network administrator can draw a logical circle around any portion of the network. We'll call the portion of the network inside the circle a "region". (I apologize for making up a new term, but I want to prevent confusion with existing terms, such as "area", or "subnetwork"). LSPs inside a region will not "leak out". LSPs from outside the region will not "leak in". Information about addresses inside the region will be explicitly advertised through configured address summaries. Similarly, information about addresses outside the region will be explicitly advertised through configured address summaries. For safety, ease of network troubleshooting, and flexibility in such cases as links that should be included in multiple regions, it is convenient to assign a name to a region. An option will be added to IS-IS messages to include the region name. The goal is that regions be as autoconfiguring as possible. Ideally, only the routers on the boundary of a region will need to know anything about the region. And in a network that is small enough for a non-hierarchical level 2 network to keep track of everything, there is no necessity to configure any region information. This design should be compatible with current implementations. Although a router that has not implemented the design in this document cannot be on the boundary of a region, it should interoperate in a multi-level IS-IS net. 4. Topologies This proposal really only concerns how to make level 2 routing multi-level. It pertains to both IP and CLNP. Only CLNP has true level 1 routing, (by the definition that a node has an ID within a level 1 subnetwork and can have multiple links within that level 1 subnetwork, or move within that level 1 subnetwork, and always have just one network layer address). At any rate, this proposal does not change level 1 routing -- it only changes Perlman (Internet-Draft expires end December 1993) [Page 3] Internet-Draft Multilevel IS-IS June 1993 the nature of level 2 routing. OSPF and IS-IS refer to "areas" in the context of IP routing. This proposal makes IP areas simply a special case of regions. The basic idea is that the network will be partitioned by network management into "regions". Each region will be assigned a name, which will be a text string. LSPs do not leak between areas, however, information about the destinations within a region do get summarized and announced to other regions. The summary addresses must be configured in order to get any aggregation of addresses. Otherwise, all destinations would be reported. For example, assume there is a region A and the destinations in the region are 5.12.*, 5.17.*, and 5.22.15.*. If R has a link in region A and a link in region B, R will include information about the destinations in A in R's LSP in region B. R might have been configured with the summary address 5.* for import into B, in which case it will include 5.* in its LSP in B. If R has not been configured with a summary address, it will report the destinations 5.12.*, 5.17.*, and 5.22.15.*. For additional flexibility, a router can be configured to import only the configured address summaries into one of its regions, or be configured with summaries that it should not import into that region. A router can be in multiple regions, and a link can be in multiple regions. The scheme is flexible so that region boundaries can be done whichever way is most convenient. The way region boundaries are marked is by configuring a router as to which links are in which regions. There is an unfortunate aspect of importing information between regions, in that the counting-to-infinity behavior of distance vector protocols manifests itself, and in a particularly ugly way since each step of the counting-to-infinity behavior is done by flooding of an LSP in a region. We could eliminate the counting-to-infinity problem by constraining the topology in various ways, or by making the protocol expensive and complex by doing something like listing the entire path of regions from which information originated. However, we are advocating merely adding to the LSP information a count of the number of regions through which the information was imported. This will alleviate but not solve the counting-to-infinity problem. Further tuning can be done by configuration of import/export rules. 5. Management The design of the management for multilevel IS-IS has the following goals: Perlman (Internet-Draft expires end December 1993) [Page 4] Internet-Draft Multilevel IS-IS June 1993 - Allow networks with simple topologies to autoconfigure as much as possible. - Allow sophisticated network managers in complex topologies as much flexibility as possible. - Allow nodes to be managed one at a time. The network should do something sensible in all the intermediate states. - Allow formation of a region by configuration of only the routers in the boundary of the region. 5.1. Port/Region Mapping We will define a "region" as a portion of the network that is intended to be physically intact (we may or may not design automatic region partition repair). It has a name, which is a text string which can be optionally configured into routers that are completely inside the region, but must be configured into routers that have links to other regions. A router that has links to other regions must be configured with names for each of the regions to which it attaches, as well as a mapping between links and regions. Something like the following: region Alice: ports 1, 2, 7 region Bob: ports 3, 4 region Fred: port 5 region George: ports 6,7 Note that port 7 is in both regions George and Alice. It is legal for a link to be in multiple regions. However, once a link is in multiple regions, IS-IS packets transmitted over the link must have the region name option included. It is also legal to not configure a region name for some ports, in which case all unconfigured ports are considered to be in the same region, which is the unnamed region. 5.2. Address Summaries for Import Into Region import summaries into Alice (IP address, mask), cost (IP address, mask), cost ... Perlman (Internet-Draft expires end December 1993) [Page 5] Internet-Draft Multilevel IS-IS June 1993 (IP address, mask), cost (CLNP address prefix), cost (CLNP address prefix), cost ... (CLNP address prefix), cost exception flag (IP address, mask) is an IP address summary. (CLNP address prefix) is a CLNP address prefix. Cost does not have to be configured. If it is, then it is the cost advertised when that summary is advertised. If cost is not configured, then the cost of the nearest matching address is used as the cost to report to that address summary. The "exception flag" states what should be done about destinations that are reachable but are not included in any of the configured address prefixes. If the flag is true, then all remaining reachable destinations will be imported. If the flag is false, then nothing other than configured address prefixes will be imported. It might be convenient to allow configuration of address prefixes that are specifically disallowed, so for instance a region might allow all addresses to be imported except for a few. Another item that might be desirable is to configure a region count per address summary, to make the counting-to-infinity solution more powerful. For instance, for address summary 5.*, it might be configured for a count of 3, whereas for address summary 12.13.* it might be configured for a count of 7. This would say that when importing 5.*, unless there was at least one address matching 5.* that had a region count of at most 2, then 5.* would not be reported. If this is not configured on a per address summary basis, then each router would be configured with a single region count limit that would apply to all address summaries being imported. 6. Extra Information in Control Packets 6.1. Hello, CSNP, PSNP These packets will contain an additional field, as an option, which is "region name". If R has a link which is configured to be in multiple regions, then R will not accept any control packet on that link unless it has the "region name" option. But for links which are configured to be in only a single region, a packet that has no region name option will be accepted and Perlman (Internet-Draft expires end December 1993) [Page 6] Internet-Draft Multilevel IS-IS June 1993 assumed to be from that region. A packet received on link L with a region name for which R has not been configured for L will be rejected. 6.2. LSP The LSP contains the region name option for specifying which region the LSP belongs to (for the same purpose and used the same way as the Hello, CSNP, and PSNP). Destinations reported in an LSP are marked as "internal" or "external", plus there is a "region count" which specifies the total number of regions through which this information has been imported (to alleviate the count-to-infinity problem. 7. Using Address Summaries This is similar to the rules in integrated IS-IS for address summaries for IP. - For each (summary address), cost configured: If any address matching that summary is reachable in any other region (as known through the LSP database and Dijkstra calculation for that region), then report that summary address as reachable. If "cost" is configured, report the greater of the configured value, or the cost of the nearest address matching the summary as the cost. Otherwise, report the cost to the nearest matching address. Mark the information as "external". - If "exceptions flag" is set, then report each reachable address not already subsumed by one of the configured summaries. Note that we are assuming the IS-IS cost metric will be expanded from 6 bits. We are importing a path cost, not a link cost, so it must be possible to report a metric larger than 6 bits. Suppose (5.*, cost 17) is configured into R as an address summary to import into region B. Suppose 5.13.15 is reachable in region A (R knows this because of R's region A LSP database and Dijkstra calculation). 1. If 5.13.15 was internal in region A, then R would report (5.*, 17, region count=1) in its LSP in region B. 2. If 5.13.15 was reported with a region count of 4 in A, then Perlman (Internet-Draft expires end December 1993) [Page 7] Internet-Draft Multilevel IS-IS June 1993 R would report a region count of 5 in its LSP in region B for address prefix 5.*. 8. Picking a Path Routing is always to longest matching address prefix, regardless of cost, whether it's marked internal vs external, etc. When calculating a path to address prefix D, one being an internal path and one being an external path (and both being prefixes of exactly the same length), then the internal path is preferred regardless of cost. For instance, suppose D is announced in R1's LSP in region A as being internal, and the path cost to D (cost to R1, plus the link cost advertised in R1's LSP to D) is x. Now suppose D is also announced in R2's LSP in region B, but as being external, and the path cost to D (cost to the router announcing D, plus the link cost in the LSP to D) is y. Then regardless of the values of x or y, the packet is routed towards R1. 9. Counting-to-Infinity It is possible for region B to export address summary 5.13.14.*, and have it (or a shorter prefix, like 5.*) reimported through some other router. Especially if 5.13.14.* were to become unreachable, this would lead to a loop where 5.13.14.* would be reimported into B, exported via the same path as before, and reimported, etc. Each time the cost would increase, but it would take intolerably many iterations for the cost to increase to a large enough value to know that the address prefix was unreachable. So we include a region count. If address summary 5.* is configured for import into region B, and 5.12.* is reachable in region A, with a region count of 7, and 5.15.17.* is reachable in region C with a region count of 10, then 5.* is imported into B, with a region count of 8. It is somewhat worrisome that the region count for 5.15.17.* is decreasing, but it will not be a problem because the only way for a region count to decrease is if the address summary gets shorter -- this cannot happen over and over, since the address summary is only of finite length. If the counting behavior is too intolerable even with the region count, then we could configure per-address summary region counts, or we could screen out importation of certain address summaries that should not arrive from a particular direction. Also, if routers are configured not to report anything other than their configured address summaries, then it is possible to eliminate loops (in most topologies). Perlman (Internet-Draft expires end December 1993) [Page 8] Internet-Draft Multilevel IS-IS June 1993 It might be tempting, in order to solve the counting problem, to list an entire path of region names, instead of merely a region count. This might make the count-to-infinity converge more quickly. However, it would take too much room in the LSP (especially if a text string is used for a region name instead of, say, a one or two byte integer, globally assigned for uniqueness). And it is not clear what to list as the region name when, for instance, 5.* is being imported into B because 5.13.* is reachable in A and 5.15.* is reachable in C. Probably the right thing would be to add both A and C to the list of regions 5.* has been imported through. Another disadvantage of listing the region names is that it requires region names to be globally unique. Otherwise, a region name can be the same as another region name provided that the two regions do not touch (if they did, they'd merge). It also might be tempting to put in the "original region name", i.e. the region in which the address was internal. However, this would not solve the count-to-infinity problem except in the original region, and it is also not clear what to put as the "original region name" when, as in the example in the previous paragraph, 5.* might be being imported into B because 5.13.* was reachable internally in A and 5.15.* was reachable internally in C. Other optimizations that might be explored are to limit which routers import information. For instance, perhaps only the router that can import an address summary with the lowest cost should import that summary -- other routers would remove the address from their LSPs when they noticed it reported in a different router's LSP with lower cost. This would eliminate some routes. For instance, if router R1 reports D as reachable at cost 71 and router R2 reports D as reachable at cost 72, then routers closer to R2 would be better off routing through R2 even though R1 is closer to the destination (but the combined cost to get to the router and from there to D is less good through R1). Perhaps the right way to do the optimization of information minimization is to add information to the configuration of an address summary that tells R to report address summary D only if R does not see D reported in another router's LSP in that region at lower cost. 10. Working Group Information The current co-chairs of the ISIS working group are: Ross Callon Wellfleet Communications Inc. Perlman (Internet-Draft expires end December 1993) [Page 9] Internet-Draft Multilevel IS-IS June 1993 2 Federal Street Billerica MA 01821 USA Phone: (508) 436 3936 Email: rcallon@wellfleet.com Chris Gunner Digital Equipment Corp. 550 King Street Littleton MA 01460-1289 USA Phone: (508) 486 7792 Fax: (508) 486 5279 Email: gunner@dsmail.enet.dec.com The working group mailing list is: isis@merit.edu Subscription requests should be sent to: isis-request@merit.edu 11. Authors' Addresses Radia Perlman Digital Equipment Corp. 550 King Street Littleton MA 01460-1289 USA Phone: (508) 486 7648 Fax: (508) 486 5279 Email: perlman@dsmail.enet.dec.com Chris Gunner Digital Equipment Corp. 550 King Street Littleton MA 01460-1289 USA Phone: (508) 486 7792 Fax: (508) 486 5279 Email: gunner@dsmail.enet.dec.com Perlman (Internet-Draft expires end December 1993) [Page 10]